package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/">找树左下角的值(Find Bottom Left Tree Value)</a>
 * <p>给定一个二叉树的 根节点 root，请找出该二叉树的 <b>最底层</b> <b>最左边</b> 节点的值。</p>假设二叉树中至少有一个节点。
 * <pre>
 * 示例 1:
 *      输入: root = [2,1,3]
 *              2
 *             / \
 *            1   3
 *      输出: 1
 *
 * 示例 2:
 *      输入: [1,2,3,4,null,5,6,null,null,7]
 *                  1
 *                 / \
 *                2   3
 *               /   / \
 *              4   5   6
 *                 /
 *                7
 *      输出: 7
 * </pre>
 * <b>提示:</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是 [1,10^4]</li>
 *     <li>-2^31 <= Node.val <= 2^31 - 1 </li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/23 9:10
 */
public class LC0513FindBottomLeftValue_M {

    public int findBottomLeftValue(TreeNode root) {
        //return findBottomLeftValueByIteration(root);
        findBottomLeftValueByRecursion(root, 1);
        return firstNodeVal;
    }

    public int findBottomLeftValueByIteration(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 记录每一层的第一个节点
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode currNode = queue.poll();
                if (i == 0) {
                    ans = currNode.val;
                }
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
        }
        return ans;
    }

    int maxLevel = 0;
    int firstNodeVal = 0;

    public void findBottomLeftValueByRecursion(TreeNode node, int currLevel) {
        if (node == null) {
            return;
        }
        // 说明进入到了下一层
        if (currLevel > maxLevel) {
            maxLevel = currLevel;
            firstNodeVal = node.val;
        }
        findBottomLeftValueByRecursion(node.left, currLevel + 1);
        findBottomLeftValueByRecursion(node.right, currLevel + 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.right.left.left = new TreeNode(7);
        LC0513FindBottomLeftValue_M lc0513FindBottomLeftValue_m = new LC0513FindBottomLeftValue_M();
        System.out.println(lc0513FindBottomLeftValue_m.findBottomLeftValue(root));
    }
}
